package com.mdnote.practice.array.brackets;

/**
 * @author Rhythm-2019
 * @date 2020/10/2
 * @description 使括号有效的最少添加
 */
public class LeetCode921 {

    public static void main(String[] args) {
        LeetCode921 leetCode921 = new LeetCode921();
        System.out.println(leetCode921.minAddToMakeValid(")("));
    }
    public int minAddToMakeValid(String S) {
        if (S.length() == 0) {
            return 0;
        }
        // 暴力发
        int left_need = 0, right_need = 0;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '(') {
                // 对右括号的需求 + 1
                right_need++;
            } else {
                // 右边有需求 刚好可以消除一下
                if (right_need > 0) {
                    right_need--;
                } else {
                    // 右括号过多 需要左括号
                    left_need++;
                }
            }
        }

        return left_need + right_need;
    }
}
